package joq;

import java.util.NoSuchElementException;
import java.util.Observable;
import java.util.Observer;

/**
 * @author Jeff Ober<jeffober@gmail.com>
 * SkewHeap is an extremely fast, efficient (ammortized) leftist heap. It
 * supports fast merge operations with other heaps and shallow copying to
 * permit "queue unions".
 * <p>
 * SkewHeap implements a min-heap with regard to type E's compareTo method.
 * <p>
 * Of interest in this implementation is the ability to remove nodes from
 * anywhere in the heap with the same efficiency as removing the head element
 * (O(log n) ammortized). SkewHeap.Node will register with any Observable E and
 * delete itself from the tree when receiving the string argument, "DELETE".
 * @author jeff
 * @param <E> a Comparable,Observable type
 * @todo synchronization
 */
public class SkewHeap<E extends Observable & Comparable<E>>
{
    /**
     * Enumerates signals used by nodes. Currently, only DELETE is supported.
     */
    public enum SIGNAL
    {
	DELETE
    }
    /**
     * The root node of the tree.
     */
    private Node root;
    /**
     * Tracks the number of entries in the tree.
     */
    private int count;

    /**
     * Creates an empty SkewHeap.
     */
    public SkewHeap()
    {
	count = 0;
    }

    /**
     * Creates a SkewHeap using elements returned from an Iterator.
     * @param it an Iterable returning elements of type E
     */
    public SkewHeap(Iterable<E> it)
    {
	this();
	for (E elt : it)
	    push(elt);
    }

    /**
     * Returns the number of items in the heap.
     * @return the number of items in the heap
     */
    public int size()
    {
	return count;
    }

    /**
     * Recursively merges two Nodes into a new Node in-place.
     * @param a
     * @param b
     * @return the combined sub-tree
     */
    private Node merge(Node a, Node b)
    {
	if (a == null)
	    return b;

	if (b == null)
	    return a;

	Node lesser, greater, tmp;

	if (a.compareTo(b) > 0) {
	    greater = a;
	    lesser = b;
	} else {
	    greater = b;
	    lesser = a;
	}

	tmp = merge(greater, lesser.right);
	lesser.setRight(lesser.left);
	lesser.setLeft(tmp);

	return lesser;
    }

    /**
     * Inserts a value into the heap.
     * @param value the value to insert
     */
    public void push(E value)
    {
	root = merge(root, new Node(value, this));
	++count;
    }

    /**
     * Returns the least element off the heap or null if the heap is empty.
     * @return
     */
    public E poll()
    {
	if (root == null)
	    return null;

	Node popped = root;
	root = merge(root.left, root.right);
	--count;

	popped.value.deleteObserver(popped);

	return popped.value;
    }

    /**
     * Removes the least value and returns it. Throws NoSuchElementException if
     * the heap is empty.
     * @return the least item in the heap
     * @throws NoSuchElementException heap empty
     */
    public E pop()
    {
	E popped = poll();
	if (popped == null)
	    throw new NoSuchElementException();
	else
	    return popped;
    }

    /**
     * Returns true if there are no items in this heap.
     * @return true if there are no items in this heap
     */
    public boolean isEmpty()
    {
	return size() == 0;
    }

    /**
     * Merges this and another SkewHeap together.
     * @param other the other SkewHeap to merge
     */
    public void merge(SkewHeap<E> other)
    {
	root = merge(root, other.root);
	count = (root == null) ? 0 : root.count();
    }

    /**
     * Returns a nicely formatted representation of the heap.
     * @return
     */
    @Override
    public String toString()
    {
	return "<SkewHeap (" + count + " items) >";
    }

    /**
     * Prints out the tree for debugging.
     */
    public void explain()
    {
	if (root != null) {
	    System.out.println(this);
	    root.explain(1);
	} else
	    System.out.println(this);
    }

    /**
     * Produces a semi-shallow copy of this SkewHeap, with a structure
     * independent of the source, but containing references to the same values.
     * <p>
     * In conjunction with an Observable E, this permits the following situation:
     * SkewHeaps A and B are combined into C. When an element is removed from C,
     * it may then signal A and B, removing the same node efficiently from three
     * heaps.
     * <p>
     * <b>Note:</b> when an element is popped off of the heap, it does not signal
     * its deletion automatically. This is left to the caller who receives the
     * value.
     * @return a new SkewHeap containing shared values
     */
    public SkewHeap<E> shallowCopy()
    {
	SkewHeap<E> newHeap = new SkewHeap<E>();
	if (root != null)
	    newHeap.root = root.shallowCopy(newHeap);
	return newHeap;
    }

    /**
     * An individual node in a SkewHeap.
     */
    public class Node implements Comparable<Node>, Observer
    {
	private final E value;
	private Node left, right, parent;
	private SkewHeap<E> heap;

	/**
	 * Constructs a Node for value.
	 * @param value the value of the node
	 * @param heap the parent heap container
	 */
	Node(E value, SkewHeap<E> heap)
	{
	    this.value = value;
	    this.heap = heap;
	    value.addObserver(this);
	}

	/**
	 * Updates this node based on the signal sent (param 'arg'). Currently,
	 * the only supported signal is the string, SkewHeap.SIGNAL.DELETE,
	 * which causes the node to prune itself from the SkewHeap. Deleting a
	 * node from within loses the value, although this is a non-issue, since
	 * it is the value itself doing the signaling.
	 * @param o an Observable object
	 * @param arg the signal, (e.g. SkewHeap.SIGNAL.DELETE)
	 */
	public void update(Observable o, Object arg)
	{
	    if (arg == SkewHeap.SIGNAL.DELETE)
		destruct();
	}

	/**
	 * Removes this node from the tree in-place, attaching its children to
	 * its parent as a newly merged sub-tree. Note that the value of the
	 * node is lost, although this is usually a non-issue, as this method
	 * is only called from update(), which is signaled from the value.
	 * @see update
	 */
	private void destruct()
	{
	    // Case 1: this node is the root of the skew heap
	    if (heap.root == this) {
		heap.pop();
		return;
	    }

	    // Case 2: this node has already been destroyed
	    if (this.parent == null)
		throw new NoSuchElementException("orphan node");

	    // Case 2: this node is internal to the skew heap
	    if (parent.left == this)
		parent.setLeft(heap.merge(left, right));
	    else
		parent.setRight(heap.merge(left, right));

	    this.left = null;
	    this.right = null;
	    this.parent = null;
	    this.heap = null;
	}

	/**
	 * Returns a nicely formatted string.
	 * @return
	 */
	@Override
	public String toString()
	{
	    String p = (parent == null) ? "NULL" : parent.value.toString();
	    return "<Node value='" + value + "' parent='" + p + "' >";
	}

	/**
	 * Sets this.left to newLeft, updating parent links.
	 * @param newLeft the new left child node
	 */
	private void setLeft(Node newLeft)
	{
	    if ((left = newLeft) != null)
		left.parent = this;
	}

	/**
	 * Sets this.right to newRight, updating parent links.
	 * @param newRight the new right child node
	 */
	private void setRight(Node newRight)
	{
	    if ((right = newRight) != null)
		right.parent = this;
	}

	/**
	 * Shortcut to compare two nodes' values.
	 * @param o another Node
	 * @return a positive integer if greater than o, negative if lesser, 0 if equal
	 */
	public int compareTo(Node o)
	{
	    return value.compareTo(o.value);
	}

	/**
	 * Recursively copies the tree's structure, but storing references to
	 * the same values.
	 * @param newHeap the heap to which the new nodes shall be attached
	 * @return a new Node sharing the same value
	 * @see SkewHeap.shallowCopy
	 */
	private Node shallowCopy(SkewHeap<E> newHeap)
	{
	    Node newNode = new Node(value, newHeap);
	    if (left != null)
		newNode.setLeft(left.shallowCopy(newHeap));
	    if (right != null)
		newNode.setRight(right.shallowCopy(newHeap));
	    return newNode;
	}

	/**
	 * Recursively counts the number of nodes in a tree.
	 * @return
	 */
	private int count()
	{
	    int n = 1;

	    if (left != null)
		n += left.count();
	    if (right != null)
		n += right.count();

	    return n;
	}

	/**
	 * Prints out a pretty display of the node tree for debugging. Depth
	 * tracks the current depth in the tree for indentation.
	 * @param depth the depth of recursion; used for indentation
	 */
	private void explain(int depth)
	{
	    for (int i = 0; i < depth; ++i)
		System.out.print(" ");

	    System.out.println(this);

	    if (left != null)
		left.explain(depth + 1);

	    if (right != null)
		right.explain(depth + 1);
	}
    }
}
